一、Neural Graph Fingerprint [2015]

《Convolutional Networks on Graphs for Learning Molecular Fingerprints》

1. 在材料设计领域的最新工作已经将神经网络用于材料筛选，其任务是通过学习样本来预测新型分子的特性。预测分子特性通常需要将分子图作为输入，然后构建模型来预测。在分子图中节点表示原子，边表示化学键。这个任务的一个难点在于：输入的分子图可以具有任意大小和任意形状，而大多数机器学习模型只能够处理固定尺寸、固定形状的输入。目前SOTA的方法是通过hash 函数对分子图进行预处理从而生成固定尺寸的指纹向量（fingerprint vector），该指纹向量作为分子的特征灌入后续的模型中。在训练期间，分子指纹（molecular fingerprint ）被视为固定（fixed）的（即，固定指纹）。

   论文《Convolutional Networks on Graphs for Learning Molecular Fingerprints》 提出了神经图指纹 （neural graph fingerprint）模型，该模型用一个可微的神经网络代替了分子指纹部分。神经网络以原始的分子图作为输入，采用卷积层来抽取特征，然后通过全局池化来结合所有原子的特征。这种方式使得我们可以端到端的进行分子预测。

   相比较传统的固定指纹的方式，神经图指纹具有以下优势：

   • 预测能力强：通过实验比较可以发现，神经图指纹比传统的固定指纹能够提供更好的预测能力。

   • 模型简洁：为了对所有可能的子结构进行编码，固定指纹的必须维度非常高。而神经图指纹只需要对相关特征进行编码，模型的维度相对而言低得多，这降低了下游的计算量和正则化需求。

   • 可解释性：传统的固定指纹对每个片段（fragment）进行不同的编码，片段之间没有相似的概念。在神经图指纹中，每个特征都可以由相似但是不同的分子片段激活，这使得特征的representation 更具有意义。

     即，相似的片段具有相似的特征，相似的特征也代表了相似的片段。

2. 相关工作：这项工作在精神上类似于神经图灵机（ neural Turing machine: NTM），从某种意义上讲，我们采用现有的离散计算架构，并使每个部分可微从而进行 gradient-based 的优化。

   • 卷积神经网络：卷积神经网络已被用于对图像、语音、时间序列进行建模。然而，标准卷积架构使用固定的、网格的 graph数据结构，这使得它很难应用于具有不同尺寸或结构的对象（如分子）。最近 《A convolutional neural network for modelling sentences》 开发了一种卷积神经网络架构，可用于对不同长度的句子进行建模。

   • 神经指纹（neural fingerprint）：最密切相关的工作是 《Deep architectures and deep learning in chemoinformatics: the prediction of aqueous solubility for drug-like molecules》 ，它构建了一个具有 graph-valued 输入的神经网络。它的方法是删除所有的环 （cycle）并将graph 构建为 tree 结构，选择一个原子作为 root，然后从叶节点到 root 节点运行 RNN 从而产生固定尺寸的 representation 。因为具有 $N$$N$ 个节点的 graph 有 $N$$N$ 个可能的 root，所有需要构建 $N$$N$ 个可能的 graph 。最终的 descriptor 是所有不同的图计算的 representation 的 sum 。这种方法的计算成本为 $O(N^2{F}^2)$$O(N^2F^2)$，其中 $N$$N$ 为原子数量，$F$$F$ 为特征向量维度，因此不太适合大分子。

   • 定量构效关系（quantitative structure-activity relationship: QSAR）的神经网络：预测分子性质的现代标准是结合圆形指纹（circular fingerprint）以及全连接神经网络（或者其它回归方法）。

     • 《Multi-task neural networks for QSAR predictions》 使用圆形指纹作为神经网络、高斯过程、随机森林的输入。

     • 《Massively multitask networks for drug discovery》 使用圆形指纹（深度为 2）作为多任务神经网络的输入，并表明多任务有助于提高性能。

   • fixed graph 上的神经网络：《Spectral networks and locally connected networks on graphs》 在图结构固定的情况下在图上引入卷积网络，每个训练样本的不同之处仅在于：在同一个图的不同节点具有不同的特征。相比之下，我们的网络解决了每个训练样本都是不同图的情况。

   • input-dependent graph 上的神经网络：

     • 《The graph neural network model》 提出了一种用于图的、具有一个有趣训练过程的神经网络模型。前向传播包括运行消息传递方案（message-passing scheme）从而达到平衡，这一事实（即，不动点）允许在不存储整个前向计算的情况下计算反向梯度。他们将他们的模型应用于预测分子化合物的诱变性、以及网页排名。

     • 《Neural network for graphs: A contextual constructive approach》 还提出了一种用于图的神经网络模型。该模型具有一个 learning scheme ，其内循环优化的不是训练损失，而是每个新提出（newly-proposed ）的向量与训练误差残差之间的相关性。他们将他们的模型应用于 150 种分子化合物的沸点数据集上。

     我们的论文建立在这些思想的基础上，具有以下区别：我们的方法用简单的、gradient-based 的优化代替了复杂的训练算法，推广了现有的圆形指纹计算，并将这些神经网络应用于现代的 QSAR pipeline 上下文中（这些 pipeline 在指纹特征之上使用神经网络来增加模型容量）。

   • 被展开（unrolled）的推断算法：《Deep unfolding: Model-based inspiration of novel deep architectures》 和其他人已经注意到迭代式的推断过程有时类似于 RNN 的前馈计算。这些想法的一个自然扩展是参数化每个 inference step ，并训练神经网络从而仅使用少量迭代来近似地 match 精确推断的输出。从这个角度来看，神经指纹类似于原始图上被展开的消息传递算法。

1.1 模型

1.1.1 圆形指纹算法

1. 分子指纹（molecular fingerprint）的最新技术是扩展连接性圆形指纹 （extended-connectivity circular fingerprints: ECFP）。ECFP 是对Morgan 算法的改进，旨在以无关于原子标记顺序（atom-relabling）的方式来识别分子中存在哪些子结构（substructure）。

   ECFP 通过对前一层邻域的特征进行拼接，然后采用一个固定的哈希函数来抽取当前层的特征。哈希函数的结果视为整数索引，然后对节点 feature vector 在索引对应位置处填写 1 (即，登记某个特定的子结构是否出现) 。

   不考虑hash 冲突，则指纹向量的每个索引都代表一个特定的子结构。索引表示的子结构的范围取决于网络深度，因此网络的层数也被称为指纹的“半径”。

   ECFP 类似于卷积网络，因为它们都在局部采用了相同的操作，并且在全局池化中聚合信息。

2. ECFP 的计算框架如下图所示：首先通过分子结构构建分子图，其中节点表示原子、边表示化学键。在每一层，信息在邻域之间流动。图的每个节点在一个固定的指纹向量中占据一个bit。

   其中这只是一个简单的示意图，实际上每一层都可以写入指纹向量。

   指纹向量 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$ 仅记录了每个子结构是否出现，但是无法记录这些子结构出现的频次。

   

3. 圆形指纹算法：

   • 输入：

     • 分子结构

     • 半径参数 $R$$R$

     • 指纹向量长度 $S$$S$

   • 输出：指纹向量 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$

   • 算法步骤：

     • 初始化指纹向量：

       $$\overrightarrow{\mathbf{f}}=(\underset{S}{\underbrace{0,0,\cdots ,0}}{)}^{\mathrm{\top }}$$

     • 遍历每个原子 $a$$a$ ，获取每个原子的特征 ${\overrightarrow{\mathbf{r}}}_a^{(0)}=g(a)$$\mathbf{\vec r}_a^{(0)} = g(a)$ 。

     • 遍历每一层。对于第 $l,1\le l\le R$$l, 1\le l\le R$ 层，迭代步骤为：

       • 遍历分子中的每个原子 $a$$a$ ，对原子 $a$$a$ 计算：

         • 获取节点 $a$$a$ 邻域原子的特征：${\overrightarrow{\mathbf{r}}}_1^{(l-1)},\cdots ,{\overrightarrow{\mathbf{r}}}_N^{(l-1)}$$\mathbf{\vec r}_1^{(l-1)},\cdots,\mathbf{\vec r}_N^{(l-1)}$ ，其中 $N$$N$ 为邻域原子数量。

         • 拼接节点 $a$$a$ 及其邻域原子特征：${\overrightarrow{\mathbf{v}}}^{(l)}=[{\overrightarrow{\mathbf{r}}}_a^{(l-1)},{\overrightarrow{\mathbf{r}}}_1^{(l-1)},\cdots ,{\overrightarrow{\mathbf{r}}}_N^{(l-1)}]$$\mathbf{\vec v}^{(l)} = \left[\mathbf{\vec r}_a^{(l-1)},\mathbf{\vec r}_1^{(l-1)},\cdots,\mathbf{\vec r}_N^{(l-1)}\right]$ 。

         • 执行哈希函数得到节点 $a$$a$ 的当前特征：${\overrightarrow{\mathbf{r}}}_a^{(l)}=\text{hash}\left({\overrightarrow{\mathbf{v}}}^{(l)}\right)$$\mathbf{\vec r}_a^{(l)} = \text{hash}\left(\mathbf{\vec v}^{(l)}\right)$ 。

         • 执行索引函数：$i=\text{mod}({\overrightarrow{\mathbf{r}}}_a^{(l)},S)$$i = \text{mod}\left(\mathbf{\vec r}_a^{(l)},S\right)$ 。

         • 登记索引：$f_i=1$$f_i = 1$ 。

     • 最终返回 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$ 。

1.1.2 分子指纹GCN算法

1. 我们选择类似于现有ECFP 的神经网络架构，用可微函数来代替 ECFP 中的每个离散操作：

   • 哈希操作（Hashing）：在ECFP 算法中，应用于每一层的哈希函数的目的是为了组合关于每个原子及其邻域子结构的信息。这确保了 fragment 中的任何修改，无论多么小，都将导致激活不同的指纹索引（ fingerprint index ）。

     我们利用单层神经网络代替哈希运算。当分子的局部结构发生微小的变化时（神经网络是可微的，因此也是平滑的），这种平滑函数可以得到相似的激活值。

   • 索引操作（Indexing）：在 ECFP 算法中，每一层采用索引操作的目的是将每个原子的特征向量组合成整个分子指纹。每个原子在其特征向量的哈希值确定的索引处，将指纹向量的单个比特位设置为1，每个原子对应一个1 。这种操作类似于池化，它可以将任意大小的graph 转换为固定大小的向量。当分子图比较小而指纹长度很大时，最终得到的指纹向量非常稀疏。

     我们使用softmax 操作视作索引操作的一个可微的近似。本质上这是要求将每个原子划分到一组类别的某个类别中。所有原子的这些类别向量的sum 得到最终的指纹向量。其操作也类似于卷积神经网络中的池化操作。

   • 规范化（Canonicalization）：无论原子的邻域原子的顺序如何变化，圆形指纹是不变的。实现这种不变性的一种方式是：在算法过程中，根据相邻原子的特征和键特征对相邻原子进行排序。我们尝试了这种排序方案，并且还对局部邻域的所有可能排列应用了局部特征变换。

     另外，一种替代方案是应用排序不变函数（permutation-invariant）， 如求和。为了简单和可扩展性，我们选择直接求和。

2. 神经图指纹算法：

   • 输入：

     • 分子结构

     • 半径参数 $R$$R$

     • 指纹长度 $S$$S$

     • 隐层参数 ${\mathbf{H}}_1^1,\cdots ,{\mathbf{H}}_R^5$$\mathbf H_1^1,\cdots, \mathbf H_R^5$， 输出层参数 ${\mathbf{W}}_1,\cdots ,{\mathbf{W}}_R$$\mathbf W_1,\cdots,\mathbf W_R$ 。

       对不同的键数量，采用不同的隐层参数 $1,2,3,4,5$$1,2,3,4,5$ （最多五个键）。

       即，不同邻域大小使用不同的隐层参数 $\mathbf{H}$$\mathbf H$ 。

   • 输出：指纹向量 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$

   • 算法步骤：

     • 初始化指纹向量：

       $$\overrightarrow{\mathbf{f}}=(\underset{S}{\underbrace{0,0,\cdots ,0}}{)}^{\mathrm{\top }}$$

     • 遍历每个原子 $a$$a$ ，获取每个原子的特征 ${\overrightarrow{\mathbf{r}}}_a=g(a)$$\mathbf{\vec r}_a = g(a)$ 。

     • 遍历每一层。对于第 $l,1\le l\le R$$l, 1\le l\le R$ 层，迭代步骤为：

       • 遍历分子中的每个原子 $a$$a$ ，对原子 $a$$a$ 计算：

         • 获取节点 $a$$a$ 邻域原子的特征：${\overrightarrow{\mathbf{r}}}_1^{(l-1)},\cdots ,{\overrightarrow{\mathbf{r}}}_N^{(l-1)}$$\mathbf{\vec r}_1^{(l-1)},\cdots,\mathbf{\vec r}_N^{(l-1)}$，其中 $N$$N$ 为邻域原子数量。

         • 池化节点 $a$$a$ 及其邻域 ${\mathcal{N}}_a$$\mathcal N_a$ 的原子的特征：${\overrightarrow{\mathbf{v}}}^{(l)}={\overrightarrow{\mathbf{r}}}_a^{(l-1)}+\sum _{i=1}^N{\overrightarrow{\mathbf{r}}}_i^{(l-1)}$$\mathbf{\vec v}^{(l)} = \mathbf{\vec r}_a^{(l-1)}+\sum_{i=1}^N\mathbf{\vec r}_i^{(l-1)}$ 。

         • 执行哈希函数：${\overrightarrow{\mathbf{r}}}_a^{(l)}=\sigma \left({\mathbf{H}}_l^N{\overrightarrow{\mathbf{v}}}^{(l)}\right)$$\mathbf{\vec r}_a^{(l)} = \sigma\left(\mathbf H_l^N \mathbf{\vec v}^{(l)}\right)$ ， $N$$N$ 为邻域节点数量。

         • 执行索引函数：$\overrightarrow{\mathbf{i}}=\text{softmax}\left({\mathbf{W}}_l{\overrightarrow{\mathbf{r}}}_a^{(l)}\right)$$\mathbf{\vec i} = \text{softmax}\left(\mathbf W_l\mathbf{\vec r}_a^{(l)}\right)$ 。

         • 登记索引：$\overrightarrow{\mathbf{f}}=\overrightarrow{\mathbf{f}}+\overrightarrow{\mathbf{i}}$$\mathbf{\vec f} = \mathbf{\vec f} + \mathbf{\vec i}$ 。

     • 最终返回 $\overrightarrow{\mathbf{f}}$$\mathbf{\vec f}$ 。

3. 设指纹向量的长度为 $S$$S$ ，节点特征向量的维度为 $F$$F$ ，则 ${\mathbf{W}}_l$$\mathbf W_{l}$ 的参数数量为 $O(F\times S)$$O(F\times S)$，${\mathbf{H}}_l^N$$\mathbf H_l^N$ 的参数数量为 $O(F\times F)$$O(F\times F)$ 。

4. 上述 ECFP 算法和神经图指纹算法将每一层计算得到的指纹叠加到全局指纹向量中。我们也可以针对每一层计算得到一个层级指纹向量，然后将它们进行拼接，而不是相加。以神经图指纹算法为例：

   • 在第 $l$$l$ 层计算索引为：${\overrightarrow{\mathbf{i}}}^{(l)}=\text{softmax}\left({\mathbf{W}}_l{\overrightarrow{\mathbf{r}}}_a^{(l)}\right)$$\mathbf{\vec i}^{(l)} = \text{softmax}\left(\mathbf W_l\mathbf{\vec r}_a^{(l)}\right)$ 。然后登记索引：${\overrightarrow{\mathbf{f}}}^{(l)}={\overrightarrow{\mathbf{f}}}^{(l)}+{\overrightarrow{\mathbf{i}}}^{(l)}$$\mathbf{\vec f} ^{(l)}= \mathbf{\vec f} ^{(l)}+ \mathbf{\vec i}^{(l)}$ 。

   • 最终将所有层的索引拼接：$\overrightarrow{\mathbf{f}}=[{\overrightarrow{\mathbf{f}}}^{(1)},{\overrightarrow{\mathbf{f}}}^{(2)},\cdots ,{\overrightarrow{\mathbf{f}}}^{(R)}]$$\mathbf{\vec f} = \left[\mathbf{\vec f}^{(1)} ,\mathbf{\vec f}^{(2)} ,\cdots,\mathbf{\vec f}^{(R)} \right]$ 。

5. ECFP 圆形指纹可以解释为具有较大随机权重的神经图指纹算法的特殊情况。

   • 在较大的输入权重情况下，当 $\sigma (\cdot )$$\sigma(\cdot)$ 为 $\tanh (\cdot )$$\tanh(\cdot)$ 时，该激活函数接近阶跃函数。而级联的阶跃函数类似于哈希函数。

   • 在较大的输入权重情况下，softmax 函数接近一个one-hot 的 argmax 操作，这类似于索引操作。

1.1.3 限制

1. 计算代价：神经图指纹在原子数、网络深度方面与圆形指纹具有相同的渐进复杂度，但是由于在每一步都需要通过矩阵乘法来执行特征变换，因此还有附加的计算复杂度。

   假设分子的特征向量维度为 $F$$F$ ，指纹向量长度为 $S$$S$ ，网络深度为 $R$$R$ ，原子数量为 $N$$N$ ，则神经图指纹的计算复杂度为 $O(RNFS+RN{F}^2)$$O(RNFS + RNF^2)$ 。

   在实践中，在圆形指纹上训练一个单隐层的神经网络只需要几分钟，而对神经图指纹以及指纹顶部的单隐层神经网络需要一个小时左右。

2. 每层的计算限制：从网络的一层到下一层之间应该采取什么结构？本文采用最简单的单层神经网络，实际上也可以采用多层网络或者 LSTM 结构，这些复杂的结构可能效果更好。

3. 图上信息传播的限制：图上信息传播的能力受到神经网络深度的限制。对于一些规模较小的图如小分子的图，这可能没有问题；对于一些大分子图， 这可能受到限制。最坏情况下，可能需要深度为 $\frac{N}{2}$$\frac N2$ 的网络来处理规模（以原子数来衡量）为 $N$$N$ 的图。

   为了缓解该问题，《Spectral networks and locally connected networks on graphs》 提出了层次聚类，它只需要 $\log N$$\log N$ 层就可以在图上传播信息。这种方式需要解析分子为树结构，可以参考NLP 领域的相关技术。

4. 无法区分立体异构体（stereoisomers ）：神经图指纹需要特殊处理来区分立体异构体，包括 enantomers 对映异构体（分子的镜像）、cis/trans isomers 顺/反异构体（绕双键旋转）。大多数圆形指纹的实现方案都可以区分这些异构体。

1.2 实验

1.2.1 随机权重

1. 分子指纹的一个用途是计算分子之间的距离。这里我们检查基于 ECFP 的分子距离是否类似于基于随机的神经图指纹的分子距离。

   我们选择指纹向量的长度为 2048，并使用Jaccard 相似度来计算两个分子的指纹向量之间的距离：

   $$\text{distance}(\overrightarrow{\mathbf{x}},\overrightarrow{\mathbf{y}})=1-\frac{\sum _{i}min(x_i,y_i)}{\sum _{i}max(x_i,y_i)}$$

   我们的数据集为溶解度数据集，下图为使用圆形指纹和神经图指纹的成对距离散点图，其相关系数为 $r=0.823$$r=0.823$ 。

   图中每个点代表：相同的一对分子，采用圆形指纹计算到的分子距离、采用神经图指纹计算得到的分子距离，其中神经图指纹模型采用大的随机权重。距离为1.0 代表两个分子的指纹（圆形指纹或神经图指纹）没有任何重叠，距离为0.0 代表两个分子的指纹圆形指纹或神经图指纹）完全重叠。

   

2. 我们将圆形指纹、随机神经图指纹接入一个线性回归层，从而比较二者的预测性能。

   • 圆形指纹、大的随机权重的随机神经图指纹，二者的曲线都有类似的轨迹。这表明：通过大的随机权重初始化的随机神经图指纹和圆形指纹类似。

   • 较小随机权重初始化的随机神经图指纹，其曲线与前两者不同，并且性能更好。

     这表明：即使是未经训练的神经网络，它相对平滑的激活值也能够有助于模型的泛化。

   

1.2.2 可解释性

1. 圆形指纹向量的特征（即某一组bit 的组合）只能够通过单层的单个fragment 激活（偶然发生的哈希碰撞除外），神经图指纹向量的特征可以通过相同结构的不同变种来激活，从而更加简洁和可解释。

   为证明神经图指纹是可解释的，我们展示了激活指纹向量中每个特征对应的子结构类别。

   • 溶解性特征：我们将神经图指纹模型作为预测溶解度的线性模型的输入来一起训练。下图展示了对应的fragment（蓝色），这些fragment可以最大程度的激活神经图指纹向量中最有预测能力的特征。

     • 上半图：激活的指纹向量的特征与溶解性具有正向的预测关系，这些特征大多数被包含亲水性R-OH 基团（溶解度的标准指标）的fragment所激活。

     • 下半图：激活的指纹向量的特征与溶解性具有负向的预测关系（即：不溶解性），这些特征大多数被非极性的重复环结构所激活。

     

   • 毒性特征：我们用相同的架构来预测分子毒性。下图展示了对应的fragment（红色），这些fragment可以最大程度的激活神经图指纹向量中最有预测能力的特征。

     • 上半图：激活的指纹向量的特征与毒性具有正向的预测关系，这些特征大多数被包含芳环相连的硫原子基团的fragment所激活。

     • 下半图：激活的指纹向量的特征与毒性具有正向的预测关系，这些特征大多数被稠合的芳环（也被称作多环芳烃，一种著名的致癌物）所激活。

     

1.2.3 模型比较

1. 数据集：我们在多个数据集上比较圆形指纹和神经图指纹的性能：

   • 溶解度数据集：包含 1144 个分子，及其溶解度标记。

   • 药物功效数据集：包含 10000 个分子，及其对恶行疟原虫（一种引发疟疾的寄生虫）的功效。

   • 有机光伏效率数据集：哈佛清洁能源项目使用昂贵的 DFT 模拟来估算有机分子的光伏效率，我们从该数据集中使用 20000 个分子作为数据集。

2. 配置：我们的 pipeline 将每个分子编码的 SMILES 字符串作为输入，然后使用 RDKit 将其转换为graph 。我们也使用 RDKit 生成的扩展圆形指纹作为 baseline 。这个过程中，氢原子被隐式处理。

   我们的 ECFP 和神经网络中用到的特征包括：

   • 原子特征：原子元素类型的 one-hot、原子的度（degree）、连接氢原子的数量、隐含价（implicit valence）、极性指示（aromaticity indicator）。

   • 键特征：是否单键、是否双键、是否三键、是否芳族键、键是否共轭、键是否为环的一部分。

3. 我们采用 Adam 优化算法，训练步数为 10000，batch size = 100 。我们还使用了 batch normalization 技术。

   我们还对神经网络进行了 tanh 和 relu 激活函数的对比实验，我们发现relu 在验证集上一直保持优势并且优势不大。

   我们还对神经网络进行了 drop-connect 实验，它是 dropout 的一个变种，其中权重被随机设置为零（而不是隐单元被随机设置为零）。我们发现这会导致更差的验证误差。

4. 我们使用 Random-Search 来优化以下超参数：学习率的对数 、初始权重的对数、$L_2$$L_2$ 正则化系数的对数、指纹向量长度 $S$$S$ 、指纹深度 $R$$R$ （最深六层）、全连接网络层的维度、神经图指纹的隐层维度。

   所有超参数使用 $k$$k$ 折交叉验证来优化，其中每一折随机执行50 次。

5. 我们比较了两种情况下圆形指纹和神经图指纹的性能：

   • 第一种情况：一个线性层使用指纹向量作为输入来执行预测，即 linear layer。

   • 第二种情况：一个单隐层的神经网络使用指纹向量作为输入来执行预测，即 neural net 。

   结果如下图所示。可以看到在所有实验中，神经图指纹均达到或者超过圆形指纹的性能，并且使用神经网络层的方式（neural net ）超过了线性层的方式（linear layer）。